Many recent advances have been made in data storage and communications media. However, the explosive proliferation of information and the continuous growth of data applications are outgrowing technological advances in storage devices and communication tools. Data compression offers an attractive approach to alleviate many of the problems associated with data proliferation. Among its many benefits are reduction in data storage requirements, reduction in the cost of communication within distributed networks, reduction in the cost of backup and recovery in computer systems, increased security and efficient search operations on compressed index structure of files. In recent years, the demand for data compression and the need to develop faster and more efficient compression methods has increased considerably due to the increased usage of data compression with scientific and statistical databases, document delivery systems and communications networks.
Virtually all data compression techniques to date have been software implementations which do not meet the projected speed and performance requirements of future systems. Generally applicable hardware for use in compressing data from uniform length binary codes to variable length binary codes such as Huffman codes, are not available. Such equipment could, however, be used to good advantage throughout the design of an operating system, a file subsystem or a data base management system.
Proposals for hardware assistance for data compression have been few and of only limited application.
An early proposal for hardware for compression/decompression of text data is described in Lea, "Text Compression with Associative Parallel Processors," The Computer Journal, Vol. 21, No. 1, 1978, pp. 45-46. That scheme uses a stand-alone device comprising an associative parallel processor (APP), a character queue (buffer), access ports and switches. The APP has an associative memory array, input and output registers and a microprogram store. The compression method uses a 200 entry dictionary (i.e. look-up table) stored in the APP memory as a list of &lt;n-gram, code&gt; pairs for text compression of frequently occurring letter combinations, e.g. &lt;THE, c1&gt;, &lt;TION, c2&gt;, &lt;AN, c3&gt;. During compression, characters are loaded into the character queue and a search is initiated. If an n-gram is located, the corresponding code is generated as output; otherwise, a single character from the queue is passed to output. In either case, the appropriate number of characters is loaded into the character queue. The Lea article estimates that such a text compression device could operate at rates up to 0.64 Mbytes/second for compression and 0.91 Mbytes/second for decompression.
Another proposal, described in Hazboun and Bassiouni, "A Multi-group technique for Data Compression," Proc. ACM SIGMOD Int. Conf. on Management of Data, 1982, pp. 284-292, is a primitive design for the multi-group compression method which is designed to reduce the overhead of data transmission in distributed networks. The proposed hardware is an I/O board in a host machine, logically based on a finite state machine. It comprises a decode machine (input register, control logic, first-in-first-out (FIFO) character queue, address register and microcode memory), an encode machine (primary and alternative send registers, a FIFO character queue, transmit control logic, look-ahead logic and three flag bits) and an encode/decode memory. The heart of the finite state machine is the single instruction processor whose task is to climb through a logic tree of binary decisions. The microcode memory holds the necessary jump addresses, with one or two jump addresses being selected based on the current data bit being received.
A third proposal, given in Hawthorn, "Microprocessor Assisted Tuple Access Decompression and Assembly for Statistical Data Base Systems," Proc. VLDB, 1982, pp. 223-233, uses a microprocessor assisted system (MAS) to offload the process of data compression and attribute partitioning from the front-end machine running a statistical data base management system. The general purpose microprocessors are organized in a two level hierarchy. At the top level, there is a single (root) microprocessor which is connected to both the front-end machine and to the leaf microprocessors (at the second level of the hierarchy). Each disk in the system is connected to a leaf microprocessor. Hawthorn estimated that at least 1300 instructions would be executed by a microprocessor for compression of a 2 Kbyte page. Thus, at an execution speed of 1 microinstruction per second, a compression rate of up to 1.57 Mbytes/second would be attainable.
In Welch, "A Technique for High-Performance Data Compression," Computer, Vol. 17, No. 6, 1984, pp. 8-19, there is a brief discussion about the Sperry hardware-design of the LZW algorithm. That design uses an 8K RAM as a hash table with a load factor of 0.5. The speed depends on the hashing system. Welch estimated that compression speeds of up to half the clock rate could be possible with a compression ratio of 50% and short hash lengths.
In Gonzalez-Smith and Storer, "Parallel Algorithms for Data Compression," JACM, Vol. 32, No. 2, April 1985, pp. 344-373, there is a proposal for the implementation of compression by textual substitution, using systolic arrays. Both static and sliding dictionary models are considered. In the static dictionary case, for example, the basic element of the systolic structure is a pipe with three processing components, each pipe corresponding to a string in the dictionary. The overall structure is in the form of three parallel rows of elements, with dictionary strings being stored in the middle row. No estimate was given for the size of the dictionary that could be placed on a single chip.